1015D - Walking Between Houses - CodeForces Solution


constructive algorithms greedy *1600

Please click on ads to support us..

Python Code:

n,k,s=map(int,input().split())
if (n-1)*k<s or k>s:print('NO');exit()
print('YES')
q=s//k
r=s%k
pos=1
d=[1,-1]
for i in range(k):
	if i<r:pos+=d[i%2]*(q+1)
	else:pos+=d[i%2]*(q)
	print(pos,end=' ')

C++ Code:

#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;*/

// file I/O
/*ifstream ifs("input.txt");
ofstream ofs("output.txt");
#define cin ifs
#define cout ofs*/

/* ------------------------------------ */

template <typename T>
ostream& operator <<(ostream& output, const vector<T>& data) {
    for (const T& x : data)
        output << x <<" ";
    return output;
}
 
template<typename T>
istream& operator>>(istream& input,vector<T>& data) {
    for (auto& item : data)
        input >> item;
    return input;
}

/* ------------------------------------ */

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))

#define endl "\n"

const ll inf = 1e18;
const ll mod = 1e9 + 7;
const int MAX = 2e5+5;

/////////////////////////////////////////////

void solve() {
    ll n,k,s; cin>>n>>k>>s;
    if((n-1)*k < s || s < k) {
    	cout<<"NO\n";
    	return;
    }
    cout<<"YES\n";
    ll start = 1;
    while(k--) {
    	 ll curr = min(s - k, n - 1);
    	 s -= curr;
    	 if(start + curr <= n) start += curr;
    	 else start -= curr;
    	 cout<<start<<" ";
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll tc=1; 
    // cin>>tc;
    for(ll i=1; i<=tc; ++i) {
    	solve();
    }
    return 0;
}


Comments

Submit
0 Comments
More Questions

528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable